package org.misty.practices.algorithm.tree;

import org.jetbrains.annotations.NotNull;

import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

public class HuffmanTree implements Comparable<HuffmanTree> {
    private char data;
    private short weight;
    private HuffmanTree left;
    private HuffmanTree right;

    public HuffmanTree(char data, short weight) {
        this.data = data;
        this.weight = weight;
    }

    public HuffmanTree(HuffmanTree left, HuffmanTree right, short weight) {
        this.left = left;
        this.right = right;
        this.weight = weight;
    }

    @Override
    public int compareTo(@NotNull HuffmanTree o) {
        return this.weight - o.weight;
    }

    @Override
    public String toString() {
        return "HuffmanTree{" +
                "data=" + data +
                ", weight=" + weight +
                '}';
    }

    public static HuffmanTree create(Map<Character, Short> map) {
        if (map.size() == 0) {
            return null;
        }
        var list = new LinkedList<HuffmanTree>();
        for (var me : map.entrySet()) {
            list.offer(new HuffmanTree(me.getKey(), me.getValue()));
        }
        while (list.size() > 1) {
            Collections.sort(list);
            var x = list.pop();
            var y = list.pop();
            var node = new HuffmanTree(x, y, (short) (x.weight + y.weight));
            list.push(node);
        }
        return list.pop();
    }

    public static void main(String[] args) {
        var map = new HashMap<Character, Short>();
        map.put('A', (short) 27);
        map.put('B', (short) 8);
        map.put('C', (short) 15);
        map.put('D', (short) 15);
        map.put('E', (short) 30);
        map.put('F', (short) 5);
        var tree = create(map);
        System.out.println(tree);
    }
}
